/*
package chapter10.arrays.other.backtracking;

import chapter10.arrays.other.Article;

*/
/**
 * Created by lili on 2017/7/1.
 *//*

//10.3.4   回溯法
//【例10.5】 回溯法求解0-1背包问题。
//① 物品按重量降序排序，按背包重量约束剪枝和按物品重量限界剪枝，求出所有可用解，再比较选择最优解。

public class Knapsack01
{
    private float kweight;                                 //背包重量
    private Article arts[];                                //保存若干物品
    private int x[];                                       //保存一个解（n元组）
    private int count=0;                                   //解的个数
    private int selection[];                               //保存一个最优解
    private float maxprice=0;                              //背包最大价值

    //构造方法，输出所有解、可用解及最优解，kweight指定背包重量，arts指定若干物品，物品件数为arts.length
    public Knapsack01(float kweight, Article arts[])
    {
        this.kweight = kweight;
        this.arts = arts;
        this.x = new int[arts.length];                     //保存一个可用解
        Knapsack01_weight();                               //① 按物品重量限界剪枝
        Knapsack01_weightPrice();                          //② 按物品重量和价值限界剪枝
    }

    //① 物品按重量降序排序，按背包重量约束剪枝和按物品重量限界剪枝，求出所有可用解，再比较选择最优解。
    private void Knapsack01_weight()
    {
        System.out.println("①  物品按重量降序排序");
        java.util.Arrays.sort(this.arts, this.arts[0]);
        //数组排序，由Comparator对象（arts元素）指定排序依据（按重量降序）
        System.out.println(this.arts.length+"件物品(重量,价值,单位重量价值)：");
        print(this.arts);                                  //输出物品序列，输出一维数组，方法体略
        System.out.println("选项，背包重量，背包价值：");
        enumerate(0,this.arts.length);                     //穷举法输出所有选项，递归回溯
        System.out.println(this.count+"个选项");

        this.selection = new int[this.arts.length];        //保存最优解
        this.count=0;
        this.maxprice=0;
        System.out.println("可用解，背包重量，背包价值：");
        backtrack(0, 0, 0);                                //递归回溯，按物品重量限界剪枝
        System.out.println(this.count+"个可用解，最优解是");
        print(this.selection);                             //输出最优解，方法体省略
    }

    private void enumerate(int i, int n)                   //穷举法输出所有选项，递归回溯
    {
        if (i<n)
            for (int j=1; j>=0; j--)
            {
                this.x[i]=j;                               //x[i]取值为0或1
                enumerate(i+1, n);
            }
        else                                               //i==n，到达叶子结点，获得一个n元组
        {
            this.count++;                                  //计数
            print(this.x);                                 //输出一个解，输出一维数组x，方法体省略
        }
    }

    //递归回溯，测试物品i装入与否情况，weight、price指定背包当前重量和价值
    //①  物品按重量降序排序，按背包重量约束剪枝和按物品重量限界剪枝
    private void backtrack(int i, float weight, float price)
    {
        if (i<this.arts.length)
        {
            if (weight+this.arts[i].weight<=this.kweight)  //若背包不超重，约束剪枝
            {
                this.x[i]=1;                               //装入物品i
                backtrack(i+1, weight+this.arts[i].weight, price+this.arts[i].price);
                //进入左子树，测试下一物品，背包重量和价值增加
            }
            this.x[i]=0;                                   //没有装入物品i
            if (getTotalWeight(i+1)>=this.kweight-weight)  //若剩余物品能装满背包，限界剪枝
                backtrack(i+1, weight, price);             //进入右子树，测试下一物品，背包重量和价值没变
        }
        else                                               //到达叶子结点，获得一个n元组
        {
            this.count++;                                  //解个数计数
            print(this.x);                                 //输出一个解，输出一维数组，方法体略
            if (price>this.maxprice)                       //保存装满背包的最优解
            {
                this.maxprice = price;                     //记得背包最大价值
//                System.arraycopy(x, 0, selection, 0, x.length);//复制x数组到selection数组
                for (int j=0; j<this.x.length; j++)        //复制x数组到selection数组，记得最优解
                    this.selection[j] = this.x[j];
            }
        }
    }

    private float getTotalWeight(int i)                    //返回从i开始的剩余物品总重量
    {
        float weight=0;
        for (int j=i; j<this.arts.length; j++)
            weight += this.arts[j].weight;
        return weight;
    }

    private void print(Object table[])                     //输出物品序列
    {
        for (int i=0; i<table.length; i++)
            System.out.print(table[i].toString()+"  ");
        System.out.println();
    }
    private void print(int x[])                            //输出一个解
    {
        System.out.print("("+x[0]);
        for (int i=1; i<x.length; i++)
            System.out.print(","+x[i]);
        System.out.print(")，重量(");
        int kweight=0, kprice=0;
        for (int i=0; i<x.length; i++)
        {
            if (x[i]==1)
            {
                System.out.print(arts[i].weight);
                kweight+=arts[i].weight;
                kprice+=arts[i].price;
            }
            else
                System.out.print(0);
            if (i<x.length-1)
                System.out.print(",");
        }
        System.out.print(")="+kweight+"，价值(");
        for (int i=0; i<x.length; i++)
        {
            if (x[i]==1)
                System.out.print(arts[i].price);
            else
                System.out.print(0);
            if (i<x.length-1)
                System.out.print(",");
        }
        System.out.println(")="+kprice);
    }

    //② 按物品重量和价值限界剪枝
    private void Knapsack01_weightPrice()
    {
        System.out.println("\n②  物品按单位重量价值降序排序");
        java.util.Arrays.sort(this.arts);  //数组按单位重量价值降序排序，默认Comparable接口指定排序依据
        System.out.println(this.arts.length+"件物品(重量,价值,单位重量价值)：");
        print(this.arts);                                  //输出物品序列，输出一维对象数组，方法体省略

        this.count=0;
        System.out.println("选项，背包重量，背包价值：");
        enumerate(0,this.arts.length);                     //穷举法输出所有选项，递归回溯
        System.out.println(this.count+"个选项");

        this.count=0;
        this.maxprice=0;
        System.out.println("解，背包重量，背包价值：");
        backtrack(0, 0, 0);                                //递归回溯
    }

    public static void main(String args[]) throws Exception
    {
        Article arts[]={new Article(9,18),new Article(2,3),new Article(6,8),new Article(4,7)};//没排序
        new Knapsack01(15, arts);                //指定背包重量和物品序列，输出可用解和最优解

        Article arts2[]={new Article(9,18),new Article(3,13),new Article(2,3),new Article(6,8),new Article(4,7)};
        new Knapsack01(15, arts2);
    }
}
*/
/*
程序运行结果如下：
①  物品按重量降序排序
4件物品(重量,价值,单位重量价值)：
(9,18, 2.00)  (6,8, 1.33)  (4,7, 1.75)  (2,3, 1.50)
选项，背包重量，背包价值：
(1,1,1,1)，重量(9,6,4,2)=21，价值(18,8,7,3)=36
(1,1,1,0)，重量(9,6,4,0)=19，价值(18,8,7,0)=33
(1,1,0,1)，重量(9,6,0,2)=17，价值(18,8,0,3)=29
(1,1,0,0)，重量(9,6,0,0)=15，价值(18,8,0,0)=26
(1,0,1,1)，重量(9,0,4,2)=15，价值(18,0,7,3)=28
(1,0,1,0)，重量(9,0,4,0)=13，价值(18,0,7,0)=25
(1,0,0,1)，重量(9,0,0,2)=11，价值(18,0,0,3)=21
(1,0,0,0)，重量(9,0,0,0)=9，价值(18,0,0,0)=18
(0,1,1,1)，重量(0,6,4,2)=12，价值(0,8,7,3)=18
(0,1,1,0)，重量(0,6,4,0)=10，价值(0,8,7,0)=15
(0,1,0,1)，重量(0,6,0,2)=8，价值(0,8,0,3)=11
(0,1,0,0)，重量(0,6,0,0)=6，价值(0,8,0,0)=8
(0,0,1,1)，重量(0,0,4,2)=6，价值(0,0,7,3)=10
(0,0,1,0)，重量(0,0,4,0)=4，价值(0,0,7,0)=7
(0,0,0,1)，重量(0,0,0,2)=2，价值(0,0,0,3)=3
(0,0,0,0)，重量(0,0,0,0)=0，价值(0,0,0,0)=0
16个选项
可用解，背包重量，背包价值：
(1,1,0,0)，重量(9,6,0,0)=15，价值(18,8,0,0)=26
(1,0,1,1)，重量(9,0,4,2)=15，价值(18,0,7,3)=28
2个可用解，最优解是
(1,0,1,1)，重量(9,0,4,2)=15，价值(18,0,7,3)=28

②  物品按单位重量价值降序排序
4件物品(重量,价值,单位重量价值)：
(9,18, 2.00)  (4,7, 1.75)  (2,3, 1.50)  (6,8, 1.33)
选项，背包重量，背包价值：
(1,1,1,1)，重量(9,4,2,6)=21，价值(18,7,3,8)=36
(1,1,1,0)，重量(9,4,2,0)=15，价值(18,7,3,0)=28
(1,1,0,1)，重量(9,4,0,6)=19，价值(18,7,0,8)=33
(1,1,0,0)，重量(9,4,0,0)=13，价值(18,7,0,0)=25
(1,0,1,1)，重量(9,0,2,6)=17，价值(18,0,3,8)=29
(1,0,1,0)，重量(9,0,2,0)=11，价值(18,0,3,0)=21
(1,0,0,1)，重量(9,0,0,6)=15，价值(18,0,0,8)=26
(1,0,0,0)，重量(9,0,0,0)=9，价值(18,0,0,0)=18
(0,1,1,1)，重量(0,4,2,6)=12，价值(0,7,3,8)=18
(0,1,1,0)，重量(0,4,2,0)=6，价值(0,7,3,0)=10
(0,1,0,1)，重量(0,4,0,6)=10，价值(0,7,0,8)=15
(0,1,0,0)，重量(0,4,0,0)=4，价值(0,7,0,0)=7
(0,0,1,1)，重量(0,0,2,6)=8，价值(0,0,3,8)=11
(0,0,1,0)，重量(0,0,2,0)=2，价值(0,0,3,0)=3
(0,0,0,1)，重量(0,0,0,6)=6，价值(0,0,0,8)=8
(0,0,0,0)，重量(0,0,0,0)=0，价值(0,0,0,0)=0
16个选项
最优解，背包重量，背包价值：
(1,1,1,0)，重量(9,4,2,0)=15，价值(18,7,3,0)=28
(1,0,0,1)，重量(9,0,0,6)=15，价值(18,0,0,8)=26



①  物品按重量降序排序
5件物品(重量,价值,单位重量价值)：
(9,18, 2.00)  (6,8, 1.33)  (4,7, 1.75)  (3,13, 4.33)  (2,3, 1.50)
选项，背包重量，背包价值：
(1,1,1,1,1)，重量(9,6,4,3,2)=24，价值(18,8,7,13,3)=49
(1,1,1,1,0)，重量(9,6,4,3,0)=22，价值(18,8,7,13,0)=46
(1,1,1,0,1)，重量(9,6,4,0,2)=21，价值(18,8,7,0,3)=36
(1,1,1,0,0)，重量(9,6,4,0,0)=19，价值(18,8,7,0,0)=33
(1,1,0,1,1)，重量(9,6,0,3,2)=20，价值(18,8,0,13,3)=42
(1,1,0,1,0)，重量(9,6,0,3,0)=18，价值(18,8,0,13,0)=39
(1,1,0,0,1)，重量(9,6,0,0,2)=17，价值(18,8,0,0,3)=29
(1,1,0,0,0)，重量(9,6,0,0,0)=15，价值(18,8,0,0,0)=26
(1,0,1,1,1)，重量(9,0,4,3,2)=18，价值(18,0,7,13,3)=41
(1,0,1,1,0)，重量(9,0,4,3,0)=16，价值(18,0,7,13,0)=38
(1,0,1,0,1)，重量(9,0,4,0,2)=15，价值(18,0,7,0,3)=28
(1,0,1,0,0)，重量(9,0,4,0,0)=13，价值(18,0,7,0,0)=25
(1,0,0,1,1)，重量(9,0,0,3,2)=14，价值(18,0,0,13,3)=34
(1,0,0,1,0)，重量(9,0,0,3,0)=12，价值(18,0,0,13,0)=31
(1,0,0,0,1)，重量(9,0,0,0,2)=11，价值(18,0,0,0,3)=21
(1,0,0,0,0)，重量(9,0,0,0,0)=9，价值(18,0,0,0,0)=18
(0,1,1,1,1)，重量(0,6,4,3,2)=15，价值(0,8,7,13,3)=31
(0,1,1,1,0)，重量(0,6,4,3,0)=13，价值(0,8,7,13,0)=28
(0,1,1,0,1)，重量(0,6,4,0,2)=12，价值(0,8,7,0,3)=18
(0,1,1,0,0)，重量(0,6,4,0,0)=10，价值(0,8,7,0,0)=15
(0,1,0,1,1)，重量(0,6,0,3,2)=11，价值(0,8,0,13,3)=24
(0,1,0,1,0)，重量(0,6,0,3,0)=9，价值(0,8,0,13,0)=21
(0,1,0,0,1)，重量(0,6,0,0,2)=8，价值(0,8,0,0,3)=11
(0,1,0,0,0)，重量(0,6,0,0,0)=6，价值(0,8,0,0,0)=8
(0,0,1,1,1)，重量(0,0,4,3,2)=9，价值(0,0,7,13,3)=23
(0,0,1,1,0)，重量(0,0,4,3,0)=7，价值(0,0,7,13,0)=20
(0,0,1,0,1)，重量(0,0,4,0,2)=6，价值(0,0,7,0,3)=10
(0,0,1,0,0)，重量(0,0,4,0,0)=4，价值(0,0,7,0,0)=7
(0,0,0,1,1)，重量(0,0,0,3,2)=5，价值(0,0,0,13,3)=16
(0,0,0,1,0)，重量(0,0,0,3,0)=3，价值(0,0,0,13,0)=13
(0,0,0,0,1)，重量(0,0,0,0,2)=2，价值(0,0,0,0,3)=3
(0,0,0,0,0)，重量(0,0,0,0,0)=0，价值(0,0,0,0,0)=0
32个选项
可用解，背包重量，背包价值：
(1,1,0,0,0)，重量(9,6,0,0,0)=15，价值(18,8,0,0,0)=26
(1,0,1,0,1)，重量(9,0,4,0,2)=15，价值(18,0,7,0,3)=28
(0,1,1,1,1)，重量(0,6,4,3,2)=15，价值(0,8,7,13,3)=31
3个可用解，最优解是
(0,1,1,1,1)，重量(0,6,4,3,2)=15，价值(0,8,7,13,3)=31

②  物品按单位重量价值降序排序
5件物品(重量,价值,单位重量价值)：
(3,13, 4.33)  (9,18, 2.00)  (4,7, 1.75)  (2,3, 1.50)  (6,8, 1.33)
选项，背包重量，背包价值：
(1,1,1,1,1)，重量(3,9,4,2,6)=24，价值(13,18,7,3,8)=49
(1,1,1,1,0)，重量(3,9,4,2,0)=18，价值(13,18,7,3,0)=41
(1,1,1,0,1)，重量(3,9,4,0,6)=22，价值(13,18,7,0,8)=46
(1,1,1,0,0)，重量(3,9,4,0,0)=16，价值(13,18,7,0,0)=38
(1,1,0,1,1)，重量(3,9,0,2,6)=20，价值(13,18,0,3,8)=42
(1,1,0,1,0)，重量(3,9,0,2,0)=14，价值(13,18,0,3,0)=34
(1,1,0,0,1)，重量(3,9,0,0,6)=18，价值(13,18,0,0,8)=39
(1,1,0,0,0)，重量(3,9,0,0,0)=12，价值(13,18,0,0,0)=31
(1,0,1,1,1)，重量(3,0,4,2,6)=15，价值(13,0,7,3,8)=31
(1,0,1,1,0)，重量(3,0,4,2,0)=9，价值(13,0,7,3,0)=23
(1,0,1,0,1)，重量(3,0,4,0,6)=13，价值(13,0,7,0,8)=28
(1,0,1,0,0)，重量(3,0,4,0,0)=7，价值(13,0,7,0,0)=20
(1,0,0,1,1)，重量(3,0,0,2,6)=11，价值(13,0,0,3,8)=24
(1,0,0,1,0)，重量(3,0,0,2,0)=5，价值(13,0,0,3,0)=16
(1,0,0,0,1)，重量(3,0,0,0,6)=9，价值(13,0,0,0,8)=21
(1,0,0,0,0)，重量(3,0,0,0,0)=3，价值(13,0,0,0,0)=13
(0,1,1,1,1)，重量(0,9,4,2,6)=21，价值(0,18,7,3,8)=36
(0,1,1,1,0)，重量(0,9,4,2,0)=15，价值(0,18,7,3,0)=28
(0,1,1,0,1)，重量(0,9,4,0,6)=19，价值(0,18,7,0,8)=33
(0,1,1,0,0)，重量(0,9,4,0,0)=13，价值(0,18,7,0,0)=25
(0,1,0,1,1)，重量(0,9,0,2,6)=17，价值(0,18,0,3,8)=29
(0,1,0,1,0)，重量(0,9,0,2,0)=11，价值(0,18,0,3,0)=21
(0,1,0,0,1)，重量(0,9,0,0,6)=15，价值(0,18,0,0,8)=26
(0,1,0,0,0)，重量(0,9,0,0,0)=9，价值(0,18,0,0,0)=18
(0,0,1,1,1)，重量(0,0,4,2,6)=12，价值(0,0,7,3,8)=18
(0,0,1,1,0)，重量(0,0,4,2,0)=6，价值(0,0,7,3,0)=10
(0,0,1,0,1)，重量(0,0,4,0,6)=10，价值(0,0,7,0,8)=15
(0,0,1,0,0)，重量(0,0,4,0,0)=4，价值(0,0,7,0,0)=7
(0,0,0,1,1)，重量(0,0,0,2,6)=8，价值(0,0,0,3,8)=11
(0,0,0,1,0)，重量(0,0,0,2,0)=2，价值(0,0,0,3,0)=3
(0,0,0,0,1)，重量(0,0,0,0,6)=6，价值(0,0,0,0,8)=8
(0,0,0,0,0)，重量(0,0,0,0,0)=0，价值(0,0,0,0,0)=0
32个选项
最优解，背包重量，背包价值：
(1,0,1,1,1)，重量(3,0,4,2,6)=15，价值(13,0,7,3,8)=31
(0,1,1,1,0)，重量(0,9,4,2,0)=15，价值(0,18,7,3,0)=28
(0,1,0,0,1)，重量(0,9,0,0,6)=15，价值(0,18,0,0,8)=26


*//*




*/
